package Leetcode第一期;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;

/**
 * @author : K k
 * @date : 18:48 2020/9/14
 * 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
 *
 *  
 *
 * 示例:
 *
 * 输入: n = 10
 * 输出: 12
 * 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
 * 说明:  
 *
 * 1 是丑数。
 * n 不超过1690。
 */
public class 丑数_49 {

    //堆+集合 效率极低 不推荐
    public int nthUglyNumber(int n) {
        //用小顶堆存放数字,自动排序
        Queue<Long> queue=new PriorityQueue<Long>();
        //Set判断是否出现过
        Set<Long> set=new HashSet<>();
        int count=0;
        long result=1;
        queue.add(result);

        while(count<n){
            result=queue.poll();
            if (!set.contains(result)){
                count++;//数字的序号
                set.add(result);
                queue.add(2*result);
                queue.add(3*result);
                queue.add(5*result);
            }
        }
        return (int)result;
    }

    //动态规划  dp[i]=min{2*a,3*b,5*c}
    public int nthUglyNumberA(int n) {
        int count=0;
        int[] dp=new int[n];
        dp[0]=1;
        int a=0,b=0,c=0;
        while (count<n-1){
            count++;
            int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
            dp[count] = Math.min(Math.min(n2, n3), n5);
            if (dp[count]==n2){a++;}
            if (dp[count]==n3){b++;}
            if (dp[count]==n5){c++;}
        }
        return dp[count];
    }

    public static void main(String[] args) {
        丑数_49 x=new 丑数_49();
        System.out.println(x.nthUglyNumberA(10));
    }
}
